1. Technical Field
The present invention relates primarily to the control of data in a network, and to methods and systems for enabling the policing of use of networks such as the Internet for communicating data.
2. Related Art
Importance of Responsible Reaction to Network Congestion
The current Internet architecture is often criticized for trusting hosts to respond voluntarily to congestion; an oversight commonly put down to the environment of mutual trust in which these algorithms emerged. Unresponsive applications can effectively steal whatever share of bottleneck resources they need from responsive flows. Although it is believed that the large majority of current sources behave well, free-riding is more than just irritating. At the most alarmist, without knowing what makes the current co-operative consensus stable, we may unwittingly destabilize it, leading to congestion collapse with no way back. But a more gradual erosion threatens the Internet's viability, because unresponsive applications require more capacity investment per average bandwidth. New Quality of Service (“QoS”) products that manage congestion properly will never be viable if anyone can take whatever they want anyway, without contributing to the investment needed. But investment in these new services will be too risky, creating a gap for even more misbehaving applications. So well-behaved applications will be trapped within a vicious circle of under-investment and misbehavior.
Some applications need to be unresponsive (e.g. interactive voice, video and games). Others simply choose to be aggressive to give themselves premium service. Also, some users continuously fill their access link with more flows than others, whether deliberately (peer-to-peer file sharing) or unwittingly (worm infected zombie hosts). Even if each flow is responsive, in total more congestion results.
Characterization of Rate Adaptation Policies
The TCP rate control algorithm [7] was developed in the late 1980s in response to a major congestion collapse on the Internet. It was designed to ensure that the rate of every flow traversing the Internet rapidly adapted to the level of congestion it experienced in such a way that each flow would tend towards a rate that shared capacity of any congested router or link fairly.
The TCP rate control algorithm runs within the operating system of the sending host. The programmer of an application can choose to use it or not. Programmers of applications that cannot tolerate rapid variation of bit rate, such as interactive voice or video applications, invariably choose not to use it.
Originally the TCP algorithm characterised the path being used across the Internet by detecting losses through missing acknowledgements and by measuring the round trip delay before those acknowledgements arrived. Recently, the TCP/IP standard was improved by the optional addition of Explicit Congestion Notification (ECN), so that a router experiencing early signs of congestion could mark packets before forwarding. The acknowledgement protocol was also changed to allow these marks to be conveyed back to the source. The standard for the TCP algorithm was altered to require the sending host to respond to these returned marks as if there had been a loss.
Among many others, Padhye et al [1] have developed a formula for the long-term average of TCP flows in steady-state, which is used in particular as the guidance for the rate adjustment of TCP-Friendly Rate Control (TFRC, a rate-based version of TCP's window-based mechanism, only with smoother adaptation) [2]. When congestion remains small (m<<0.2), this value can be approximated to the square-root law, as given in Equation (1)
                    x        =                              k            ·            s                                T            ·                          m                                                          (        1        )            where x is the expectation of the throughput, k is a constant of the order of √( 3/2), s is the packet size for the flow, T is its round-trip-time, and m is the end-to-end congestion metric (as represented by the proportion of marked and dropped packets within the flow).
There exist other models for the allocation of congested network resources among concurrent flows. For instance, Crowcroft and Oechslin [6] showed how easy it was to use more capacity than others by writing a version of TCP called MulTCP with a weight parameter ω that would mimic ω parallel TCP flows. Kelly et al [3] have developed a rate control algorithm based on an economic optimisation of utilization of a network where Internet users define their own willingness-to-pay for the traffic they generate. Users effectively adopt a rate adaptation policy in order to maintain a constant spending rate over the course of the data transfer irrespective of the amount of data exchanged. The congestion status of the data path will cause the transfer duration to shrink and stretch dynamically. Such a policy is characterised by a throughput equation given in Equation (2):
                    x        =                              w            ·            s                    m                                    (        2        )            where x, m, and s have the same meaning as above while w is the willingness-to-pay parameter of the user.
All these rate control algorithms depend on metrics of the path over which the transmission is conveyed. For whatever metric, whether loss, explicit congestion or round trip delay, the current arrangements for characterizing the metric depend on the truthful compliance of both the receiver and the sender in a protocol designed to limit the rate with which they can communicate. Whole path congestion only emerges at the destination to be fed back from receiver to sender in a back-channel. But, in any data network, back-channels need not be visible to relays, as they are essentially communications between the end-points (they may be encrypted, or asymmetrically routed, or omitted entirely). So no network element can reliably intercept them. An earlier patent application by the present applicant related to a rate control mechanism that runs on network equipment intercepting acknowledgements passing back to the sender (see WO 03/049319), which has been embodied in a cellular radio network controller described in a paper later published by Siris [8]). However, such mechanisms ultimately rely on the receiver allowing its feedback to be visible and truthfully declaring path characteristics within it. Even then, the sender must also be relied upon to alter its rate correctly in response to path congestion and delay.    [1] J. Padhye, V. Firoiu, D. Towsley, and J. Kurose, “Modeling TCP Throughput: A Simple Model and its Empirical Validation”, Proc ACM SIGCOMM 1998.    [2] S. Floyd, M. Handley, J. Padhye and J. Widmer, “Equation-Based Congestion Control for Unicast Applications”. Proc. ACM SIGCOMM. August 2000.    [3] F. P. Kelly, A. K. Maulloo, and D. K. H. Tan, “Rate control for communication networks: shadow prices, proportional fairness and stability”, Journal of the Operational Research Society, 49(3):237-252, 1998.    [6] Jon Crowcroft and Philippe Oechslin, “Differentiated End to End Internet Services using a Weighted Proportional Fair Sharing TCP,” In: Computer Communication Review 28 pp. 53-69 (July, 1998).    [7] Van Jacobsen. Congestion avoidance and control. Proc. ACM SIGCOMM '88, Computer Communication Review, 18(4):314-329, 1988.
[8] Vasilios A. Siris. Resource control for elastic traffic in CDMA networks. In Proc. ACM International Conference on Mobile Computing and Networks (MobiCom '02), URL: http://www.ics.forth.gr/netlab/wireless.html, September 2002. ACM.
Rate Policing
In the current Internet, should senders stop complying with the reaction mechanism specified in the TCP standard, it would create havoc on the network. This is why several proposals have been developed for policing flows so users don't abuse their ability to send any rate of traffic over the network.
As was explained above, an Internet network element cannot currently know the relevant metrics about the path to verify that a sender is complying with the TCP protocol. Commercially available policers (e.g. from Sandvine (www.sandvine.com), or Riverhead Networks (www.riverhead.com) ensure that no flow exceeds a maximum rate, irrespective of the condition of each path being used through the rest of the network. Some such policers can use their knowledge of any local congestion on the equipment itself, but not elsewhere.
Indeed proposed policers that reduce the amount of state required by these commercial policers [4, 5, 12, 13, 14, 15, 16] must be sited on relays that are congested themselves in order to work. All these policers, which we will refer to as “bottleneck policers”, detect unusually high bit rates, but a high sending rate might be perfectly legitimate if the path is uncongested or the round-trip time is short. Similarly, other policers on the latest broadband remote access servers enforce monthly volume caps in an attempt to control high volume file-sharing. But they punish traffic that fills troughs as much as traffic that causes peaks in utilization.
Floyd and Fall [4] have proposed a penalty box mechanism based on the random early detection (RED) mechanism. RED is a widely used queue management mechanism on Internet routers, where the longer the output queue to the line, the higher is the probability of dropping (or marking if ECN is enabled) packets arriving at the queue. Their idea is to monitor the drop history of the RED algorithm. Any flow that predominates in the drop history after a long enough period is considered misbehaving, blacklisted and submitted to the appropriate sanction (dropping, declassing . . . ). CHOKe [5] also exploits the idea that a grossly misbehaving flow will appear far more in the data stream than a compliant TCP flow. Whenever a packet arrives, it is compared with another randomly picked from the queue. If the two are from the same flow, that flow is suspected of misbehaving. CHOKe shows very good results in forcing down unusually high rate traffic.
Many research proposals have made incremental improvements on techniques for rate policing initially proposed by Floyd and Fall [4]. Stabilized RED (SRED [12]) was published in parallel, while later improvements include CHOKe [5], RED with Preference Dropping (RED-PD [13]), Least Recently Used RED (LRU-RED [14]), XCHOKe [16], and Approx. Fair Dropping (AFD [15]).
However in all cases, rate is policed with no respect to the specific characteristics of the path. For instance, let us consider two flows crossing a common bottleneck: flow A with a short round-trip time passes over an otherwise barely congested path while flow B has a round trip-time four times as long and experiences four times as much congestion on its path. In the long-term, flow B should get only ⅛ of the bandwidth flow A gets. Nevertheless, with all existing policers, if congestion is elsewhere than on the network element housing the policer itself, both packets will be considered equally responsible, and flow A will therefore be much more likely to be constrained than flow B.
Clerget & Dabbous [17] have proposed another type of distributed rate policing. In their proposed framework “Tag-based Unified Fairness” (TUF), bottlenecks police traffic so that flows of a given type all get the same share of the bottleneck bandwidth. The TUF approach is capable of ensuring intra-class fairness but not inter-class fairness: if n_TCP TCP flows and n_UDP UDP flows share a bottleneck, each TCP flows will get a share x_TCP and each UDP flow will get a share x_UDP so thatn—TCP*x—TCP+n—UDP*x—UDP=C where C is the forwarding capacity of the node, however x_TCP I=x_UDP for any level of congestion other than two very specific levels. Further to not achieving inter-class fairness, the TUF approach also exhibits the weaknesses of bottleneck policers.
Also in the prior art, Raisinghani & Iyer [18] discloses a mechanism whereby a receiver dynamically prioritizes its flows by controlling the achievable congestion window they should aim for, assuming drops are all caused on the final wireless section of the path. It appears that this relates to the problem of inter-flow congestion control, and that the receiver tampers with the congestion signal in order to adjust priorities between its flow. This document includes a discussion of RED-DT, which is another single-bottleneck fairness optimisation on RED. The optimisation only relies on local information (i.e. local with respect to the node concerned), such as queue lengths, buffer size, and a number of per-flow variables all specific to the node.
A further prior art document, Nikolouzou et al [19] describes a generic Differentiated Services (DiffServ) arrangement, and addresses the definition and deployment of specific network services in a DiffServ environment.
Recently, proposals have been made to enable the rate control algorithm of a data source to quickly find out how fast it can send data across a high capacity network. In these proposals, the source places a request in a protocol field. In XCP [11], the request is in terms of how much data can be sent before any acknowledgement has been received (termed the amount of data in flight, or the congestion window). In Quick-Start [10], the field is in terms of sending rate. As a packet traverses the network, if the value of the metric that a router can tolerate is less than the request, it re-writes the field. However, the resulting field must still be returned to the sender, and the sender must ensure its future rate complies with the network's response to its request. So both schemes still depend on the co-operation of sender and receiver against their own interests. The router could remember the response it had given on the previous round, and check a source complied next time, however, this would require flow state to be held on routers, losing the benefits of the stateless connectionless model of packet forwarding characteristic of the Internet.
In connection-oriented networks, such as ATM, network elements send congestion back-pressure messages [9] along each connection, duplicating any end-to-end feedback because they don't trust it. But it is inherently hard to use similar techniques in a connectionless datagram network without losing the benefits of low connection set-up latency and robustness of a packet network.
In a co-pending application filed by the present applicant having publication number WO2005/096566 (U.S. Ser. No. 10/593,423), the subject matter of which is incorporated herein by reference, a novel feedback mechanism was proposed termed “re-feedback”, this term being indicative of the idea of “Receiver-Normalised” feedback. According to the re-feedback mechanism, the sender sets the initial value of any path characterization field so that, by the time it has accumulated path information, it tends to arrive at the destination set to a commonly standardised value. Feedback from the destination to the source is then used to continuously correct any error in the destination value when future data is sent. A principal advantage is that data effectively carries with it a “prediction” of its own downstream path for use by in-line equipment along the transmission path.
Further, in another co-pending application filed by the same applicant having publication number WO2005/109783 (U.S. Ser. No. 11/579,374), the subject matter of which is also incorporated herein by reference, a novel dropping policer was proposed that would intercept traffic to ensure the downstream path metrics (e.g. congestion or delay) within packets were not persistently negative. It used sanctions such as packet truncation or discarding. Together, embodiments of the inventions of these two applications may be used to ensure that the sender must “pre-load” a sufficiently high value into the path metric fields of each packet so that they remain positive even after having been decremented in proportion to the congestion and delay experienced during transmission across an inter-network.    [4] S. Floyd and K. Fall, “Promoting the Use of End-to-End Congestion Control in the Internet”, IEEE/ACM Transactions on Networking, May 1999.    [5] R. Pan, B. Prabhakar, and K Psounis. “CHOKe—A stateless active queue management scheme for approximating fair bandwidth allocation”.    [9] “Traffic control and congestion control in B-ISDN”. Recommendation I.371 (03/04), ITU-T, URL: http://www.itu.int/rec/recommendation.asp?type=folders&lang=e&parent=T-REC-I.371, March 2004.    [10] Amit Jain, Sally Floyd, Mark Allman, and Pasi Sarolahti. “Quick-Start for TCP and IP”. Internet Draft draft-amitquick-start-03, Internet Engineering Task Force, URL: http://www.icir.org/floyd/quickstart.html, September 2004. (Work in progress).    [11] Dina Katabi, Mark Handley, and Charlie Rohrs. “Congestion control for high bandwidth-delay product networks”. Proc. ACM SIGCOMM '02, Computer Communication Review, 32(4):89-102, October 2002.    [12] Teunis J. Ott, T. V. Lakshman, and Larry H. Wong. “SRED: Stabilized RED”. In Proc. IEEE Conference on Computer Communications (Infocom '99), pages 1346-1355, URL: http://citeseer.nj.nec.com/ott99sred.html, March 1999. IEEE.    [13] Ratul Mahajan, Sally Floyd, and David Wetheral. “Controlling high-bandwidth flows at congested router”. In Proc. IEEE International Conference on Network Protocols (ICNP '01), URL: http://citeseer.nj.nec.com/545435.html, 2001.    [14] Smitha A. L. Narasimha Reddy. “LRU-RED: An active queue management scheme to contain high bandwidth flows at congested routers”. In Proc Globecomm '01, URL: http://citeseer.nj.nec.com/473674.html, November 2001.    [15] Rong Pan, Lee Breslau, Balaji Prabhaker, and Scott Shenker. “Approximate fairness through differential dropping”. Computer Communication Review, 33(2):23-40, April 2003.    [16] P Chhabra, S Chuig, A Goel, A John, A Kumar, H Saran and R Shorey. “XCHOKE: Malicious Source Control for Congestion Avoidance at Internet Gateways”. Proc. ICNP, November 2002.    [17] Antoine Clerget & Walid Dabbous: “TUF: Tag-based Unified Fairness”, Proceedings of IEEE INFOCOM Conference on Computer Communications, April 2001.    [18] Vijay Raisinghani & Sridhar Iyer: “Analysis of receiver window control in the presence of a fair router”, IEEE Intl. Conf. on Personal and Wireless Communications, January 2005.    [19] Nikolouzou, Maniatis, Sampatakos, Tsetsekas & Venieris: “Network Services Definition and Deployment in a Differentiated Services Architecture”, IEEE Intl. Conf. on Communications 2002.